package array.slidingWindow;


/**
 * 给定一个含有n个正整数的数组和一个正整数 target 。
 * <p>
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组`[nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r]` ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 */
public class N209_MinSizeSubArrayLen {
    /**
     * 暴力法，两层循环
     */
    public int minSubArrayLen_violence(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    result = Math.min(j - i + 1, result);
                    break;
                }
            }
            if (sum < target && i == 0) return 0;
        }
        return result;
    }

    /**
     * 窗口滑动
     */
    public int minSubArrayLen_doubleIndex(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int left = 0;
        int sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                result = Math.min(right - left + 1, result);
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }


    public static void main(String[] args) {
        N209_MinSizeSubArrayLen solution = new N209_MinSizeSubArrayLen();
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 9;
        System.out.println(solution.minSubArrayLen_violence(target, nums));
        System.out.println(solution.minSubArrayLen_doubleIndex(target, nums));
    }
}
